package leetcode.hot100;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度
 */
@SuppressWarnings("all")
public class _32_最长有效括号_两次遍历 {

    /**
     * 输入：s = ")()())"
     * 输出：4
     * 解释：最长有效括号子串是 "()()"
     */
    public int longestValidParentheses(String s) {
        int left = 0, right = 0, maxlength = 0;
        // 贪心地考虑以当前字符下标结尾的有效括号长度
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * right);
            } else if (right > left) {
                left = right = 0;
            }
        }
        // 只从左往右遍历一次会漏掉一种情况，就是遍历的时候左括号的数量始终大于右括号的数量，即 (() ，
        // 这种时候最长有效括号是求不出来的
        left = right = 0;
        for (int i = len - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * left);
            } else if (left > right) {
                left = right = 0;
            }
        }
        return maxlength;
    }
}
